package 动态规划;

public class 目标和 {

    //dp未优化
    public static int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(target) > sum){
            return 0;
        }
        int t = 2 * sum + 1;
        int n = nums.length;
        int[][] dp = new int[n][t];
        if (nums[0] == 0){
            dp[0][sum] = 2;
        }else {
            dp[0][sum - nums[0]] = 1;
            dp[0][sum + nums[0]] = 1;
        }
        for (int i = 1; i <  n; i++) {
            for (int j = 0; j < t; j++) {
                dp[i][j] = (j-nums[i] >= 0? dp[i-1][j-nums[i]] : 0) + (j  + nums[i] < t ? dp[i-1][j+nums[i]] : 0);
            }
        }
        return dp[n-1][target+sum];
    }

    //利用滚动数组优化空间复杂度
    public static int findTargetSumWays1(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(target) > sum){
            return 0;
        }
        int t = 2 * sum + 1;
        int n = nums.length;
        int[] cur = new int[t];
        int[] last = new int[t];
        if (nums[0] == 0){
            last[sum] = 2;
        }else {
            last[sum - nums[0]] = 1;
            last[sum + nums[0]] = 1;
        }
        for (int i = 1; i <  n; i++) {
            for (int j = 0; j < t; j++) {
                //主要是因为如果cur[0]赋值了的话,就到最后一层循环了;所以之前cur[0]的值一直是0;
                int l = j - nums[i] >= 0 ? j - nums[i] : 0;
                int r = j + nums[i] < t ? j + nums[i] : 0;
                cur[j] = last[l] + last[r];
            }
            last = cur;
            cur = new int[t];
        }
        return last[sum+target];
    }

    //官方思路,转为0,1背包问题,
    public static int findTargetSumWays2(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (Math.abs(target) > sum || diff % 2 != 0){
            return 0;
        }
        int neg = diff / 2;
        int n = nums.length;
        //dp[i][j]表示nums前i个数凑齐j的方法数量
        int[][] dp = new int[n][sum + 1];
        dp[0][0] = 1;
        dp[0][nums[0]] += 1;
        for (int i = 1; i < n; i++) {
            System.out.println();
            for (int j = 0; j <= neg; j++) {
                //每个数都有选与不选2种选择
                dp[i][j] = dp[i-1][j - nums[i] >=0 ? j - nums[i] : sum] + dp[i-1][j];
            }
        }
        return dp[n-1][neg];
    }

    //01背包优化
    public static int findTargetSumWays3(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (Math.abs(target) > sum || diff % 2 != 0){
            return 0;
        }
        int neg = diff / 2;
        int n = nums.length;
        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = neg; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }
        return dp[neg];
    }



    public static void main(String[] args) {
        int[] nums = {0,0,0,0,0,0,0,0,1,0,0,0,0};
        System.out.println(findTargetSumWays2(nums,1));
    }
}
